import java.util.Stack;

/**
 * @Author: Liu, Yunfeng
 * @DateTime: 2020/5/17 14:19
 * @Description: 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
 * 有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。
 * 注意空字符串可被认为是有效字符串。
 */
public class IsValidBrackets {
    public static boolean isValid(String s) {
        if(s==null){
            return false;
        }
        if(s.equals("")){
            return true;
        }
        Stack<Character> stack = new Stack<>();
        stack.push(s.charAt(0));
        for(int i=1;i<s.length();i++){
           char c = s.charAt(i);
           if(c=='('||c=='['||c=='{'){
               stack.push(c);
               continue;
           }
           if(stack.empty()){
               return false;
           }
           char peek = stack.peek();
           if((peek=='{'&&c=='}')||(peek=='['&&c==']')||(peek=='('&&c==')')){
               stack.pop();
           }
           else{
               stack.push(c);
           }
        }
        if(stack.empty()){
            return true;
        }
        return false;
    }

    public static void main(String[] args){
        String s="()]{}";
        System.out.print(isValid(s));
    }
}
/*
* 利用栈，当为左括号的时候进栈
* 右括号时看是否和栈顶元素匹配
* */
